package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimize-the-difference-between-target-and-chosen-elements/
 * @create 2025/9/2 17:08
 * @since JDK17
 */

public class Solution51 {
    public int minimizeTheDifference(int[][] mat, int target) {
        int n = mat.length, m = mat[0].length, max = 0, ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            max += Arrays.stream(mat[i]).min().getAsInt();
        }
        max = Math.max(max + 70, target + 70);

        boolean[][] dp = new boolean[n + 1][max + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = max; j >= 0; j--) {
                for (int l = 0; l < m; l++) {
                    if (j >= mat[i - 1][l]) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j - mat[i - 1][l]];
                    }
                }
            }
        }
        for (int i = max; i >= 0; i--) {
            if (dp[n][i]) {
                ans = Math.min(ans, Math.abs(i - target));
            }
        }
        return ans;
    }
}
